package leetcode.code0698;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	public boolean canPartitionKSubsets(int[] nums, int k) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		if (sum % k != 0) {
			return false;
		}
		int avg = sum / k;
		int[] group = new int[k];
		return this.find(nums, avg, group, 0, k);
	}

	private boolean find(int[] nums, int avg, int[] group, int index, int k) {
		if (index == -1) {
			return k == 0;
		}
		for (int i = 0; i < group.length; i++) {
			if (group[i] + nums[index] <= avg) {
				group[i] += nums[index];
				if (this.find(nums, avg, group, index + 1, k - (group[i] == avg ? 1 : 0))) {
					return true;
				}
				group[i] -= nums[index];
			}
		}
		return false;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(true, this.canPartitionKSubsets(HelpDebug.str2array3("[4,3,2,3,5,2,1]"), 4));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
//		[10,1,10,9,6,1,9,5,9,10,7,8,5,2,10,8]
//				11
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
